4 задание ОГЭ по информатике
Тема: "Формальные описания реальных объектов и процессов"
Четвертое задание ОГЭ посвящено анализу информационных моделей - графических (граф, дерево) и табличных.
Сама суть задания заключается в поиске кратчайшего пути между населенными пунктами, представленный в виде информационных моделей.
Рассмотрим пример такого представления в табличной форме:
В таблице представлены населенные пункты A, B, C, D, E, а также связи между ними дорогами.
Между одним и тем же населенным пунктом (А - А) дороги существовать не может, поэтому пересечение закрашено серым цветом: 
Если на пересечении двух населенных пунктов стоит число, это означает, что между ними есть дорога, а число указывает на её протяженность:
На примере выше мы видим, что между населенными пунктами В и С дорога есть, и её длина равна 2.
Если же на пересечении двух пунктов пустая ячейка, значит прямая дорога между ними отсутствует:
На примере выше: дороги между Е и С - нет.
Настоятельно не рекомендуется решать это задание с помощью перебора!
Задание 1.
Между населенными пунктами А, В, С, D, E построены дороги, протяженность которых (в километрах) приведена в таблице:
Определите длину кратчайшего пути между пунктами А и E. Передвигаться можно только по дорогам, протяженность которых указана в таблице.
Решение:
Будем решать задачу двумя способами:
1 способ (построение дерева).
Будем строить дерево начиная с пункта, из которого мы выходим:
По таблице видим, что из пункта A мы можем переместиться в пункты B и C:
Из пункта B мы можем переместиться в пункты A, C и D. Но в пункт А нам не нужно, так как мы из него вышли. А любой возврат в пункт, в котором мы уже были удлиняет весь путь:
Из пункта C (который справа) мы можем переместиться в A, B или D. Опять же в пункт A нам не нужно:
Из пункта С можно попасть в А, В или D. Но тут нам не подходят уже пункты A и B, так как они в этом маршруте есть:
Продолжая аналогичные размышления и учитывая, что конечным должен быть пункт E, получим:
У нас остались не законченными пункты C и B. Не из них мы никуда уже попасть не можем, не возвращаясь, поэтому можно их убрать:
Над ребрами расставим расстояния между населенными пунктами:
Посчитаем теперь длину каждого маршрута:
И увидим, что длина самого короткого путь = 9.
Ответ: 9
2 способ (построение графа)
Разместим все наши пункты примерно по кругу:
Из таблицы нарисуем все связи между ними и подпишем расстояния:
Лучше перерисовать наш граф так, чтобы ребра не пересекались:
По графу сразу можно заметить, что самый короткий путь будет A - C - B - D - E = 9.
Но не всегда все очевидно.
Поэтому у пункта из которого мы выходим поставим рядом 0 (так как находясь в этом пункте мы еще ничего не прошли, а у всех остальных большое число, например 10000:
Далее рассуждаем следующим образом.
Если мы пойдем в пункт C, мы пройдем 0 + 3 = 3 километра. 3 < 10000, поэтому у пункта C 10000 заменяем на 3.
Аналогично, если мы пойдем в пункт B, мы пройдем 0 + 5 = 5 километров. 5 < 10000, поэтому у пункта B 10000 заменяем на 5.
Пункт A вычеркиваем.
Далее из оставшихся пунктов мы выбираем пункт с меньшим числом. Это пункт C. И начинаем такие же рассуждения.
Если мы пойдем в пункт B, мы пройдем 3 + 1 = 4 километра. 4 < 5, поэтому у пункта B 5 заменяем на 4.
Если мы пойдем в пункт В, мы пройдем 3 + 6 = 9 километров. 9 < 10000, поэтому у пункта D 10000 заменяем на 9.
Пункт C вычеркиваем.
Опять выбираем из оставшихся пункт с меньшим числом. Это пункт B.
Из него мы можем пойти только в D и тогда мы пройдем 4 + 4 = 8 километров. 9 < 9, поэтому у пункта D 9 заменяем на 8.
Пункт B вычеркиваем.
Остается только рассмотреть пункт D. Из него мы можем пойти в пункт E и пройдем 8 + 1 = 9 километров. 9<10000, поэтому у пункта E заменяем 10000 на 9. Пункт D вычеркиваем.
Итак, мы получили кратчайшее расстояние до пункта E равное 9 километров.
Плюс этого метода заключается в том, что на самом деле мы нашли кратчайшие пути из пункта А до всех остальных пунктов (это числа, которые мы ставили около пунктов).
Ответ: 9
Задание 2.
Между населенными пунктами A, B, C, D, E построены дороги, протяженность которых в (километрах) приведена в таблице.
Определите длину кратчайшего пути между пунктами A и E, проходящего через пункт С. Передвигаться можно только по дорогам, протяженность которых указана в таблице. Дважды передвигаться по любой из дорог нельзя.
Решение:
В этом задании присутствует дополнительное условие, что путь должен обязательно проходить через пункт C, но на самом деле оно только облегчает нам решение.
Построим граф:
Попытаемся опять разместить пункты так, чтобы они не пересекались. Так нам будет проще найти визуально правильное решение:
Начнем анализировать. Нам нужно в начале добраться из пункта A в пункт С. Мы можем сделать это 3 вариантами. Для каждого варианта будем рассматривать дальше, как можно быстрее всего добраться до пункта E. Не забываем, что дважды по одной и той же дороге двигаться нельзя.
1) Если мы пойдем: A - B - C. Тогда дальше кратчайшее расстояние будет C - E.
Итого весь путь: A - B - C - E = 2+3+10 = 15.
2) Если мы пойдем: A - C. Тогда дальше кратчайшее расстояние будет C - В - E.
Итого весь путь: A - С - В - E = 9+3+5 = 17.
3) Если мы пойдем: A - D - C. Тогда дальше кратчайшее расстояние будет C - В - E.
Итого весь путь: A - D - С - В - E = 4+6+3+5 = 18.
Ответ: 15
Задание 3.
Иван-Царевич спешит выручить Марью-Царевну из плена Кощея. В таблице указана протяженность дорог между пунктами, через которые он может пройти. Укажите длину самого короткого участка кратчайшего пути от Ивана-Царевича до Марьи Царевны (от точки И до точки М). Передвигаться можно только по дорогам, указанным в таблице:
Решение:
Построим граф:
Вообще, по графу очевидно, что самый короткий путь от И до М будет: И - Б - М равный 4. Но если мы ответ напишем 4, потеряем балл. Все дело в условии и в том, что нужно записать в ответ.
По условию нужно указать длину самого короткого участка кратчайшего пути.
Тогда наш кратчайший путь И - Б - М, состоит из двух участков: И - Б (длина 1) и Б - М (длина 3).
Нужно указать длину самого короткого участка, а это участок И - Б, и длина его равна 1.
Ответ: 1